package zw_701_800.ZW_744_寻找比目标字母大的最小字母;

class Solution {
    public static void main(String[] args) {
        char[] letters = {'c', 'f', 'j'};
        char target = 'a';
        char c = nextGreatestLetter(letters, target);
        System.out.println(c);

    }

    /**
     * 暴力
     *
     * @param letters
     * @param target
     * @return
     */
//    public char nextGreatestLetter(char[] letters, char target) {
//        for (int i = 0; i < letters.length; i++) {
//            if (letters[i] > target) return letters[i];
//        }
//        return letters[0];
//    }
    public static char nextGreatestLetter(char[] letters, char target) {
        // 第一个大的，小了往右、大了往左、等于往右
        int length = letters.length;
        int left = 0, right = length - 1;
        while (left + 1 < right) {
            int mid = left + ((right - left) >> 1);
            if (letters[mid] <= target) {
                left = mid;
            } else {
                right = mid;
            }
        }

        if (letters[left] > target) return letters[left];
        if (letters[right] > target) return letters[right];
        return letters[0];
    }
}
